/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

 

// 示例 1：

// 输入：
//     3
//    / \
//   9  20
//     /  \
//    15   7
// 输出：[3, 14.5, 11]
// 解释：
// 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//解法一 ： 层次遍历

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) 
    {
        vector<double> res;
        if(root == 0)
        {
            return res;
        } 
        deque<int> levels;
        deque<TreeNode*> nodes;

        nodes.push_back(root);
        levels.push_back(0);

        int currentLevel = 0;
        long int sum =0;
        int num =0;

        while(nodes.size()>0)
        {
            TreeNode* node = nodes.front();
            int l = levels.front();
            
            if(l == currentLevel)
            {
                sum += node->val;
                num ++;
            }
            else
            {
                res.push_back(double(sum)/double(num));
                currentLevel = l;
                sum = node->val;
                num=1;
            }
            if(node->left)
            {
                nodes.push_back(node->left);
                levels.push_back(l+1);
            }
            if(node->right)
            {
                nodes.push_back(node->right);
                levels.push_back(l+1);
            }  
            nodes.pop_front();
            levels.pop_front();    
        }
        res.push_back(double(sum)/double(num));
        return res;
    }
};